#pragma once
// #define DEBUG_LONGLONG
#ifdef DEBUG_LONGLONG
#include <iostream>
#endif

/**
 * 本文中涉及乘法的部分请参考 https://en.wikipedia.org/wiki/Karatsuba_algorithm
 */

// typedef unsigned int uint32_t;
// typedef unsigned short uint16_t;
// typedef unsigned char uint8_t;
#define MAX_UINT32_T 0xffffffff

typedef unsigned int uint32_t;
typedef unsigned short uint16_t;
typedef unsigned char uint8_t;

class myuint64_t {
    private:
	uint32_t high, low;

    private:
	inline uint32_t high16(const uint32_t &x) const
	{
		return x >> 16;
	}
	inline uint32_t low16(const uint32_t &x) const
	{
		return x & 0x0000ffff;
	}
	inline uint32_t add(const uint16_t &x, const uint16_t &y) const
	{
		return uint32_t(x) + uint32_t(y);
	}
	inline myuint64_t add(const uint32_t &x, const uint32_t &y) const
	{
		myuint64_t result;
		result.low = x + y;
		if (result.low < x)
			++(result.high);
		return result;
	}

	inline uint32_t mul(uint16_t x, uint16_t y) const
	{
		return uint32_t(x) * uint32_t(y);
	}

	/**
	 * @brief (ah*2^16 + al)(bh*2^16 + bl) = ah*bh*2^32 + (ah*bl +
	 * al*bh)*2^16 + al*bl
	 */
	inline myuint64_t mul(const uint32_t a, const uint32_t b) const
	{
		uint32_t ah = high16(a);
		uint32_t al = low16(a);
		uint32_t bh = high16(b);
		uint32_t bl = low16(b);

		myuint64_t result;
		result.high = ah * bh;
		result.low = al * bl;

		myuint64_t temp =
			add(ah * bl, bh * al); //这里相乘的时候不可能溢出
		result += temp << uint32_t(16);
		// std::cout << result << std::endl;
		return result;
	}

	myuint64_t(uint32_t h, uint32_t l)
		: high(h)
		, low(l)
	{
	}

    public:
	myuint64_t()
	{
		high = low = 0;
	}
	myuint64_t(const myuint64_t &x)
		: high(x.high)
		, low(x.low)
	{
	}
	// myuint64_t(const unsigned long &x)
	// 	: high(x >> 32)
	// 	, low(x & 0x00000000ffffffff)
	// {
	// }
	myuint64_t(const uint32_t &x)
		: high(0)
		, low(x)
	{
	}
	myuint64_t(const uint16_t &x)
		: high(0)
		, low(x)
	{
	}
	myuint64_t(const uint8_t &x)
		: high(0)
		, low(x)
	{
	}
	myuint64_t(const int &x)
		: high(0)
		, low(x)
	{
	}

	/*******************强制类型转换**********************/
	// operator bool() const { return (*this == myuint64_t(0)); }
#ifdef DEBUG_LONGLONG
	operator unsigned long() const
	{
		return (((unsigned long)this->high) << 32) +
		       (unsigned long)this->low;
	}
#endif
	operator char() const
	{
		return ((char)this->low);
	}
	/******************位运算**********************/

	template <typename T> myuint64_t operator&(const T &other) const
	{
		return (*this & myuint64_t(other));
	}

	myuint64_t operator&(const myuint64_t other) const
	{
		return myuint64_t(this->high & other.high,
				  this->low & other.low);
	}

	bool operator&&(const myuint64_t other) const
	{
		return ((*this != 0) && (other != 0));
	}

	/********************二元关系比较**************************/
	template <typename T> bool operator<(const T &other) const
	{
		return *this < myuint64_t(other);
	}

	bool operator<(const myuint64_t &other) const
	{
		if (this->high < other.high)
			return true;
		else if (this->high > other.high)
			return false;
		else if (this->low < other.low) //此时高位相等
			return true;
		return false;
	}

	template <typename T> bool operator>(const T &other) const
	{
		return *this > myuint64_t(other);
	}
	bool operator>(const myuint64_t &other) const
	{
		if (*this < other || *this == other)
			return false;
		else
			return true;
	}

	template <typename T> bool operator==(const T &other) const
	{
		return *this == myuint64_t(other);
	}

	bool operator==(const myuint64_t &other) const
	{
		if (this->high == other.high && this->low == other.low)
			return true;
		return false;
	}

	template <typename T> bool operator!=(const T &other) const
	{
		return *this != myuint64_t(other);
	}
	bool operator!=(const myuint64_t &other) const
	{
		return !(*this == other);
	}

	bool operator>=(const myuint64_t &other) const
	{
		return ((*this == other) || (*this > other));
	}

	bool operator<=(const myuint64_t &other) const
	{
		return ((*this == other) || (*this < other));
	}

	/*************************乘除******************************/
	myuint64_t &operator/=(const myuint64_t &other)
	{
		// TODO
		*this = *this / other;
		return *this;
	}

	template <typename T> myuint64_t operator/(const T &other) const
	{
		return (*this / myuint64_t(other));
	}

	myuint64_t operator/(const myuint64_t &other) const
	{
		if (other == myuint64_t(0))
			return 0; //防止出错
		if (other > *this)
			return uint32_t(0);
		if (other == *this)
			return uint32_t(1);
		if (other == uint32_t(1))
			return *this;
		if (other.low == 0) {
			return (this->high / other.high);
		}

		myuint64_t first, last;
		if (other.high == uint32_t(0)) {
			uint32_t l = other.low;
			last = *this;
			while (l) {
				l >>= 1;
				last >>= 1;
			}
			//此时实际的商取值范围是[last, last*2 + 1]
			first = last;
			last <<= 1;
			++last;
		}

		else {
			//此时确定有 *this > other且 other.high > 0且 other.low
			//> 0 商必然在[ah/(bh+1), ah/bh]的区间
			first = this->high / (other.high + 1);
			last = this->high / other.high;
		}

		//下面使用夹逼法

		while (last - first > 1) {
			myuint64_t temp = (first + last) >> 1;
			if (other * temp > *this)
				last = temp;
			else if (other * temp < *this)
				first = temp;
			else
				return temp;
		}
		// std::cout << "fist: " << first << std::endl;
		// std::cout << "last: " << last << std::endl;
		if (other * last <= *this)
			return last;
		else
			return first;
	}

	myuint64_t &operator*=(const myuint64_t &other)
	{
		(*this) = (*this) * other;
		return *this;
	}

	myuint64_t operator*(const myuint64_t &other) const
	{
		myuint64_t temp1 = mul(this->low, other.low);
		// printf("temp1_low: 0x%x\n", temp1.low);
		// std::cout << "temp1: " << temp1 << std::endl;
		myuint64_t temp2 = (mul(this->low, other.high) +
				    mul(this->high, other.low))
				   << 32;
		// printf("temp2_low: 0x%x\n", temp2.low);
		// std::cout << "temp2: " << temp2 << std::endl;

		myuint64_t result = temp2 + temp1;

		return result;
	}

	/************************求余**************************/
	template <typename T> myuint64_t operator%(const T &other) const
	{
		return *this - (*this / other) * other;
	}

	template <typename T> myuint64_t &operator%=(const T &other)
	{
		*this = *this % other;
		return *this;
	}

	/***********************加减***********************/

	myuint64_t &operator+=(const myuint64_t &other)
	{
		this->low += other.low;
		if (this->low < other.low)
			++(this->high);
		this->high += other.high;
		return *this;
	}

	myuint64_t operator+(const myuint64_t &other) const
	{
		myuint64_t result = *this;
		result += other;
		return result;
	}

	template <typename T> myuint64_t &operator+=(const T &c)
	{
		*this += myuint64_t(c);
		return *this;
	}

	template <typename T> myuint64_t operator+(const T &c) const
	{
		myuint64_t result = *this;
		result += myuint64_t(c);
		return result;
	}

	myuint64_t operator-(const myuint64_t &other) const
	{
		myuint64_t result = *this;
		result -= other;
		return result;
	}

	myuint64_t &operator-=(const myuint64_t &other)
	{
		if (this->low < other.low)
			--this->high;
		this->low -= other.low;
		this->high -= other.high;
		return *this;
	}

	template <typename T> myuint64_t operator-(const T &other) const
	{
		return *this - myuint64_t(other);
	}

	template <typename T> myuint64_t &operator-=(const T &other)
	{
		*this -= myuint64_t(other);
		return *this;
	}

	/***********************自增\自减*****************************/
	// Overload ++ when used as prefix
	myuint64_t &operator++()
	{
		if (low == MAX_UINT32_T) {
			++high;
		}
		++low;
		return *this;
	}

	// postfix
	myuint64_t operator++(int)
	{
		myuint64_t result = *this;
		++*this;
		return result;
	}

	// prefix
	myuint64_t &operator--()
	{
		if (low == 0) {
			--high;
		}
		--low;
		return *this;
	}

	// postfix
	myuint64_t operator--(int)
	{
		myuint64_t result = *this;
		--*this;
		return result;
	}

	/*************************左移、右移********************************/
	myuint64_t &operator<<=(const uint32_t &x)
	{
		if (x >= 64) {
			this->high = 0;
			this->low = 0;
		} else {
			//不知道为啥，反正编译器是这么实现的，如果左移的次数与位宽相同的话
			//将会左移x % 位宽，因此uint32_t左移32次就是左移0次
			if (x >= 32) {
				this->high = this->low;
				this->high <<= x - 32;
				this->low = 0;
			} else {
				this->high <<= x; //此时低x位为0b
				this->high += this->low >>
					      (32 - x); //取low的高x
							// bit
				this->low <<= x;
			}
		}

		return *this;
	}
	myuint64_t operator<<(const uint32_t &x) const
	{
		myuint64_t result = *this;
		result <<= x;
		return result;
	}
	myuint64_t operator<<(const int &x) const
	{
		return (*this << uint32_t(x));
	}

	myuint64_t &operator>>=(const uint32_t &x)
	{
		if (x >= 64) {
			this->high = 0;
			this->low = 0;
		} else {
			if (x >= 32) {
				this->low = this->high;
				this->low >>= x - 32;
				this->high = 0;
			} else {
				this->low >>= x; //此时高x位为0b
				this->low += (((1 << x) - 1) & this->high)
					     << (32 - x); //取high的低x bit
				this->high >>= x;
			}
		}
		return *this;
	}
	myuint64_t operator>>(const uint32_t &x) const
	{
		myuint64_t result = *this;
		result >>= x;
		return result;
	}

	myuint64_t operator>>(const int &x) const
	{
		return (*this >> uint32_t(x));
	}

#ifdef DEBUG_LONGLONG
	friend std::ostream &operator<<(std::ostream &out, const myuint64_t &t)
	{
		out << (unsigned long)t;
		return out;
	}
#endif
};

class myint64 : myuint64_t {
};